package com.xk._03真题骗._02链表;


import com.xk._03真题骗._00bean.Node;

import java.util.HashMap;
import java.util.Map;

/*
 * @description: https://leetcode.cn/problems/copy-list-with-random-pointer/
 * @author: xu
 * @date: 2022/10/27 22:19
 */
public class _138复制带随机指针的链表 {
    public Node copyRandomList(Node head) {
        if (head == null) return null;
        Map<Node, Node> map = new HashMap<>();
        Node curNode = head;
        while (curNode != null) {
            map.put(curNode, new Node(curNode.val));
            curNode = curNode.next;
        }
        curNode = head;
        while (curNode != null) {
            map.get(curNode).next = map.get(curNode.next);
            map.get(curNode).random = map.get(curNode.random);
            curNode = curNode.next;
        }
        return map.get(head);
    }


    public Node copyRandomList2(Node head) {
        if (head == null) return null;
        for (Node node = head; node != null; node = node.next.next){
            Node newNode = new Node(node.val);
            newNode.next = node.next;
            node.next = newNode;
        }
        for (Node node = head; node != null; node = node.next.next){
            Node newNode = node.next;
            newNode.random = node.random == null ? null : node.random.next;
        }
        Node newHead = head.next;
        for (Node node = head; node != null; node = node.next){
            Node newNode = node.next;
            node.next = newNode.next;
            newNode.next = newNode.next == null ? null : newNode.next.next;
        }
        return newHead;
    }



    Map<Node, Node> map = new HashMap<>();
    public Node copyRandomList1(Node head) {
        if (head == null) return null;
        if (!map.containsKey(head)) {
            Node newNode = new Node(head.val);
            map.put(head, newNode);
            newNode.next = copyRandomList(head.next);
            newNode.random = map.get(head.random);
        }
        return map.get(head);
    }
}
